package top.fengleifeng.question;

/**
 * @author : fengelfeing
 * @Package : top.fengleifeng.question
 * @Description:
 * @Date: 2020年10月29日5:48 下午
 */
public class Num129求根到叶子节点数字之和 {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        int count = 0;

        public int sumNumbers(TreeNode root) {
            if (root == null) {
                return 0;
            }
            StringBuilder sb = new StringBuilder();
            dfs(sb, root);
            return count;
        }

        public void dfs(StringBuilder sb, TreeNode treeNode) {
            sb.append(treeNode.val);
            if (treeNode.left == null && treeNode.right == null) {
                count = count + Integer.parseInt(sb.toString());
                sb.deleteCharAt(sb.length() - 1);
                return;
            }
            if (treeNode.left != null) {
                dfs(sb, treeNode.left);
            }
            if (treeNode.right != null) {
                dfs(sb, treeNode.right);
            }
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
//        TreeNode treeNode = new TreeNode(1);
//        treeNode.left = new TreeNode(2);
//        treeNode.right = new TreeNode(3);

        TreeNode treeNode = new TreeNode(4);
        treeNode.left = new TreeNode(9);
        treeNode.right = new TreeNode(0);
        treeNode.left.left = new TreeNode(5);
        treeNode.left.right = new TreeNode(1);
        int i = new Num129求根到叶子节点数字之和().new Solution().sumNumbers(treeNode);
        System.out.println(i);
    }
}
